package mao.leetcode.offer;

/**
 * @author Totoro
 * @date 2020/8/10
 * @explain:
 */
public class offer49 {
    public static void main(String[] args) {
        offer49 offer49 = new offer49();
        offer49.nthUglyNumber(10);
    }

    public int nthUglyNumber(int n) {
        int[] arr = new int[n];
        arr[0]=1;
        int mostIndex=0,index2=0,index3=0,index5=0,next,tmp;
        while(mostIndex < n-1){
            //需要找到乘以2,3,5最小的。
            while((tmp = arr[index2]*2) <= arr[mostIndex]) index2++;
            next = tmp;
            while((tmp = arr[index3]*3) <= arr[mostIndex]) index3++;
            next = Math.min(next,tmp);
            while((tmp = arr[index5]*5) <= arr[mostIndex]) index5++;
            next = Math.min(next,tmp);
            arr[++mostIndex] = next;
        }
        return arr[n-1];
    }
}
